package dataStructures.impl;

import dataStructures.IHeap;

/**
 * A max heap implementation of {@link IHeap} interface.
 * 
 * This implementation assumes that the index of the first element of the heap
 * is 0 and that of the last element is heapSize().
 * 
 * @author Vikas Bahirwani
 */
public class MaxHeap implements IHeap {

	int heapSize;
	int[] elements;

	/**
	 * 
	 * @param elements
	 *            int array of elements
	 */
	public MaxHeap(int[] elements) {
		this.elements = elements;
		heapSize = -1;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.IHeap#getParent(int)
	 */
	@Override
	public int getParent(int nodeIndex) {
		if (nodeIndex > heapSize) {
			return -1;
		}

		int parent = (int) Math.floor((nodeIndex + 1) / 2) - 1;

		if (parent > heapSize) {
			return -1;
		}

		return parent;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.IHeap#getLeftChild(int)
	 */
	@Override
	public int getLeftChild(int nodeIndex) {
		if (nodeIndex > heapSize) {
			return -1;
		}

		int leftChild = 2 * nodeIndex + 1;
		if (leftChild > heapSize) {
			return -1;
		}

		return leftChild;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.IHeap#getRightChild(int)
	 */
	@Override
	public int getRightChild(int nodeIndex) {

		if (nodeIndex > heapSize) {
			return -1;
		}

		int rightChild = 2 * nodeIndex + 2;
		if (rightChild > heapSize) {
			return -1;
		}

		return rightChild;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.IHeap#getHeapSize()
	 */
	@Override
	public int getHeapSize() {
		return heapSize;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.IHeap#setHeapSize(int)
	 */
	@Override
	public void setHeapSize(int i) {
		heapSize = i;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.IHeap#buildHeap()
	 */
	@Override
	public int[] buildHeap() {
		heapSize = elements.length-1;
		for (int i = (int) Math.floor(elements.length / 2) - 1; i >= 0; i--) {
			heapify(i);
		}
		return elements;

	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.IHeap#heapify(int)
	 */
	@Override
	public void heapify(int nodeIndex) {
		int largest = nodeIndex;
		int leftChild = getLeftChild(nodeIndex);
		int rightChild = getRightChild(nodeIndex);

		if ( leftChild >=0 && leftChild <= heapSize && elements[leftChild] > elements[largest]) {
			largest = leftChild;
		}

		if (rightChild>=0 && rightChild <= heapSize
				&& elements[rightChild] > elements[largest]) {
			largest = rightChild;
		}

		if (largest != nodeIndex) {
			int temp = elements[nodeIndex];
			elements[nodeIndex] = elements[largest];
			elements[largest] = temp;
			heapify(largest);
		}

		return;
	}
	
	/**
	 * @return elements
	 */
	public int[] getElements(){
		return elements;
	}

}
